#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 082. 删除排序链表中的重复元素 II.py
@time: 2022/1/14 19:59
@desc: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
> 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

@解题思路：
    1. 就硬想
    2. Ot(N), Os(1)
'''

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None
        dummy = ListNode(0, head)
        cur = dummy
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                x = cur.next.val
                # 当cur的下一个的值一直是x，则一直跳过，直到不是为止，这样就可以把涉及重复值的节点都删掉
                while cur.next and cur.next.val==x:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next